{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ML_in_Finance-Viterbi\n",
    "# Author: Matthew Dixon\n",
    "# Version: 1.0 (24.7.2019)\n",
    "# License: MIT\n",
    "# Email: matthew.dixon@iit.edu\n",
    "# Notes: tested on Mac OS X with Python 3.6 and Tensorflow 1.3.0\n",
    "# Citation: Please cite the following reference if this notebook is used for research purposes:\n",
    "# Dixon M.F., I. Halperin and P. Bilokon, Machine Learning in Finance: From Theory to Practice, Springer Graduate textbook Series, 2020. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overview\n",
    "This notebook provides a simple example of the Viterbi algorithm applied to an coin which is either fair or loaded (hidden states). Based on a sequence of observations, the algorithm will determine the most likely sequence of hidden states, i.e. whether the coin that generated the data was likely fair or loaded. The example easily maps onto financial markets, e.g. Bull or Bear, Normal or Dislocated etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def viterbi(sequence_of_observations, states, initial_probabilities, transition_probabilities, emission_probabilities):\n",
    "    V = [{}]\n",
    "    for s in states:\n",
    "        V[0][s] = {\n",
    "            'probability': initial_probabilities[s] * emission_probabilities[s][sequence_of_observations[0]],\n",
    "            'previous': None}\n",
    "    for t in range(1, len(sequence_of_observations)):\n",
    "        V.append({})\n",
    "        for s in states:\n",
    "            max_tr_probability = V[t-1][states[0]]['probability'] * transition_probabilities[states[0]][s]\n",
    "            previous_s_selected = states[0]\n",
    "            for previous_s in states[1:]:\n",
    "                tr_probability = V[t-1][previous_s]['probability'] * transition_probabilities[previous_s][s]\n",
    "                if tr_probability > max_tr_probability:\n",
    "                    max_tr_probability = tr_probability\n",
    "                    previous_s_selected = previous_s        \n",
    "            max_probability = max_tr_probability * emission_probabilities[s][sequence_of_observations[t]]\n",
    "            V[t][s] = {'probability': max_probability, 'previous': previous_s_selected}                    \n",
    "    most_likely_states = []\n",
    "    max_probability = max(value['probability'] for value in V[-1].values())\n",
    "    previous = None\n",
    "    for s, data in V[-1].items():\n",
    "        if data['probability'] == max_probability:\n",
    "            most_likely_states.append(s)\n",
    "            previous = s\n",
    "            break\n",
    "    for t in range(len(V) - 2, -1, -1):\n",
    "        most_likely_states.insert(0, V[t + 1][previous]['previous'])\n",
    "        previous = V[t + 1][previous]['previous']\n",
    "    return {'steps': most_likely_states, 'max_probability': max_probability}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sequence_of_observations = ['Heads', 'Tails', 'Tails', 'Heads', 'Tails', 'Heads', 'Heads', 'Heads', 'Tails', 'Heads']\n",
    "states = ['Fair', 'Loaded']\n",
    "initial_probabilities = {'Fair': 0.6, 'Loaded': 0.4}\n",
    "transition_probabilities = {\n",
    "    'Fair': {'Fair': 0.6, 'Loaded': 0.4},\n",
    "    'Loaded': {'Fair': 0.4, 'Loaded': 0.6}\n",
    "}\n",
    "emission_probabilities = {\n",
    "    'Fair': {'Heads': 0.5, 'Tails': 0.5},\n",
    "    'Loaded': {'Heads': 0.8, 'Tails': 0.2}\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'max_probability': 1.146617856e-05,\n",
       " 'steps': ['Fair',\n",
       "  'Fair',\n",
       "  'Fair',\n",
       "  'Fair',\n",
       "  'Fair',\n",
       "  'Loaded',\n",
       "  'Loaded',\n",
       "  'Loaded',\n",
       "  'Fair',\n",
       "  'Loaded']}"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi(sequence_of_observations,\n",
    "        states,\n",
    "        initial_probabilities,\n",
    "        transition_probabilities,\n",
    "        emission_probabilities)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
